﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【进阶】47.二叉树实现（上）
//【进阶】48.二叉树实现（下）


//【头文件包含】

#include"Heap.h"
#include"BinaryTree.h"


//【结构体声明】
/*定义一种链式树结构*/typedef struct TreeNode
{
	int val;
	struct TreeNode* leftChild;
	struct TreeNode* rightBrother;
};

//【函数声明】
void Test1();
void Test2();

//【主函数】
int main()
{

	Test1();
	Test2();

	
	return 0;
}

//【函数】

/*测试用例*/void Test1()
{
	printf("****测试用例开始****\n");

	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };

	int sz = sizeof(arr) / sizeof(arr[0]);
	Hp  heap1;
	HeapInit(&heap1, arr, sz);
	HeapPrint(&heap1);

	HeapPush(&heap1, 13);
	HeapPush(&heap1, 14);
	HeapPush(&heap1, 15);

	HeapPrint(&heap1);
	HeapPop(&heap1);
	HeapPrint(&heap1);

	HeapSort(heap1.a, heap1.size);
	HeapPrint(&heap1);
	printf("size = %d high = %d\n", heap1.size, HeapHigh(&heap1));
	HeapPrint2(&heap1);
	int returnSize = 0;
	int* arrp = NULL;
	arrp=HeapTopK_L(heap1.a, heap1.size, 4, &returnSize);
	printf("前四个最大值\n");
	for (int i = 0;i < returnSize;++i)
	{
		printf("%d ", arrp[i]);
	}
	printf("\n");
	printf("****测试用例结束****\n");

}
/*测试用例*/void Test2()
{
	printf("****测试用例开始****\n");
	//构建一颗测试用的伪二叉树
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_1 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_2 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_3 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_4 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_5 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* node_6 = (BTNode*)malloc(sizeof(BTNode));
	root->data = 1;root->left = node_1;root->right = node_2;
	node_1->data = 2;node_1->left = node_3;node_1->right = node_4;
	node_2->data = 3;node_2->left = node_5;node_2->right = node_6;
	node_3->data = 4;node_3->left = NULL;node_3->right = NULL;
	node_4->data = 5;node_4->left = NULL;node_4->right = NULL;
	node_5->data = 6;node_5->left = NULL; node_5->right = NULL;
	node_6->data = 7;node_6->left = NULL;node_6->right = NULL;

	printf("前序遍历\n");
	PrevOrder(root);
	printf("\n");
	printf("中序遍历\n");
	MidOrder(root);
	printf("\n");
	printf("后序遍历\n");
	NextOrder(root);
	printf("\n");
	printf("计算二叉树大小\n");
	int size = TreeSize(root);
	printf("size = % d\n", size);
	size=TreeLeafSize(root);
	printf("leafnums = % d\n", size);
	size = TreeDepth(root);
	printf("depth = % d\n", size);

	printf("****测试用例结束****\n");
}


//【笔记】
//47.二叉树实现（上）
	//求一个N个数的最小或最大的前K个值时分别利用建立大堆和小堆来实现
	//链式二叉树
		//遍历：1.前序、2.中序、3.后续、4.层序，其中前三者深度优先，最后一个广度优先
		//任何一个二叉树都要看成三部分：1.根节点、2.左子树、3.右子树
		// 前序遍历（先根遍历）：根-->左子树-->右子树
		// 中序遍历（中根遍历）：左子树-->根-->右子树
		// 后序遍历（后根遍历）：左子树-->右子树-->根 
		// 层序遍历（广度优先）：逐层遍历至最深（适合用队列实现）
	//单纯的二叉树做增删查改意义不大，更多的用处是利用规则实现搜索数据（红黑树、平衡二叉树等）
//47.二叉树实现（下）


